import sys
sys.path.insert(0,'..')

from rmpoly import *
from time import time
from gmpy import mpq

"""
s_n
Solve the system of polynomial equations
  fv = 0
gr = groebner_basis(fv)
solve gr[-1] = 0 and back-substitute in the other equations

i_n
Impliticization problem

inv_n  
Invariant theory
Express a polynomial p in terms of other polynomials g_n(x_1,...)
gr = groebner_basis([g_1 - i_1,...,g_n - i_n])
with i_1 < .. < i_n < x_1 < ...
p.reduce(gr)  p in term of i_1,..,i_n gives the solution

color_n
  3-coloring problem

[1] D. Cox, J. Little, D. O'Shea, Ideals, Varieties and Algorithms, 
 Springer, Third Edition, 2006

[2] Buchberger, Samos Talk at the Summer School
  Emerging Topics in Cryptographic Design and Cryptanalysis (2007)

[3] M. Paprocki talk 'Computing with polynomials in SymPy'  euroscipy2010
"""

def s1():
  """from [1] p96 """
  rp = RPoly(['z','y','x'], 8,mpq,order='lex')
  fv = [rp('x^2+y^2+z^2-1'),rp('x^2+z^2-y'),rp('x-z')]
  gr = groebner_basis(fv)
  assert gr[-1] == rp('+z^4 +1/2*z^2 -1/4')

def s2():
  """from [1] p97"""
  rp = RPoly(['z','y','x','la'], 8,mpq,order='lex')
  fv = [rp('3*x^2 + 2*y*z - 2*x*la'),rp('2*x*z-2*y*la'),rp('2*x*y - 2*z - 2*z*la'),
        rp('x^2+y^2+z^2-1')]
  gr = groebner_basis(fv)
  assert gr[-1] == rp('+z^7 -1763/1152*z^5 +655/1152*z^3 -11/288*z')
  # FIXME: previously I got the following; why?
  #assert gr[-1] == rp('+z^8 -1763/1152*z^6 +655/1152*z^4 -11/288*z^2')

def s3():
  """ from [1] p115"""
  rp = RPoly(['z','y','x'], 8,mpq,order='lex')
  fv=[rp('x^2+y+z-1'),rp('x+y^2+z-1'),rp('x+y+z^2-1')]
  gr = groebner_basis(fv)
  assert gr[-1] == rp('z^6 -4*z^4 +4*z^3 -z^2')
  
def s4():
  rp = RPoly(['y','x'], 8,mpq,order='lex')
  gr = groebner_basis([rp('x*y-1'), rp('x^3 - y^2 -1')])
  assert gr == [rp('x -y^4 -y^2'), rp('y^5 +y^3 -1')]

def i1():
  """from [1] p99"""
  rp = RPoly(['z','y','x','t'],8,mpq,order='lex')
  gr = groebner_basis([rp('t^4 - x'),rp('t^3 - y'),rp('t^2 - z')])
  assert gr[-2:] == [rp('x -z^2'),  rp('y^2 -z^3')]

def i2():
  """from [1] p100, p131"""
  rp = RPoly(['z','y','x','u','t'],8,mpq,order='lex')
  gr = groebner_basis([rp('t+u-x'),rp('t^2+2*t*u-y'),rp('t^3+3*t^2*u-z')])
  assert gr[-1] == rp('+x^3*z -3/4*x^2*y^2 -3/2*x*y*z +y^3 +1/4*z^2')
  # FIXME I had
  #assert gr == rp('x^3*z -3/4*x^2*y^2 -3/2*x*y*z +y^3 +1/4*z^2')

def inv1():
  "from [2] "
  rp = RPoly(['i1','i2','i3','x1','x2'],6,mpq)
  gr = groebner_basis([rp('-i1+x1^2+x2^2'),rp('-i2+x1^2*x2^2'),rp('-i3+x1^3*x2-x1*x2^3')])
  p = rp('x1^7*x2 - x1*x2^7')
  r = p.division(gr)[1]
  assert r == rp('-i3*i2 +i3*i1^2')
  sb = Subs(rp,rp,{'i1':rp('x1^2+x2^2'),'i2':rp('x1^2*x2^2'),'i3':rp('x1^3*x2-x1*x2^3')})
  assert sb.subs(r) == p

def color1():
   "from [2] "
   rp = RPoly(['x%d' % i for i in range(1,5)],6,mpq)
   def f(i,j):
     return rp('x%d^2+x%d*x%d+x%d^2' %(i,i,j,j))
   
   def f1(i):
     return rp('-1+x%d^3' % i)

   gr = groebner_basis([f1(1),f1(2),f1(3),f1(4), f(1,2),f(1,3),f(2,3),f(3,4)])
   assert gr == [rp('x4^2 -x4*x2 -x4*x1 +x2*x1'), rp('x3 +x2 +x1'), rp('x2^2 +x2*x1 +x1^2'), rp('x1^3 -1')]

def color2():
  """ from [3]; same example as in ../../rmpoly/bench/col_sympy.py
  but slower; in the latter case the computation is done with
  opposite lex ordering, which turns out to be faster.
  """
  V = range(1,13)
  E = [(1,2),(2,3),(1,4),(1,6),(1,12),(2,5),(2,7),(3,8),(3,10),(4,11),
    (4,9),(5,6),(6,7),(7,8),(8,9),(9,10),(10,11),(11,12),(5,12),(5,9),
    (6,10),(7,11),(8,12)]
  rp = RPoly(['x%d' % i for i in range(1,13)],10,mpq,order='lex')
  X = rp.gens()
  E = [(X[i-1],X[j-1]) for i,j in E]
  I3 = [x**3 - 1 for x in X]
  Ig = [x**2 + x*y + y**2 for x,y in E]
  I = I3 + Ig
  gr = groebner_basis(I)
  print gr

s1()
s2()
s3()
s4()
i1()
i2()
inv1()
color1()
color2()

